﻿#pragma once
#include "FormatedUtil.h"
#include "Index.h"

class ISudoku
{
public:
	/**
	 * 数独.
	 * https://www.nowcoder.com/practice/5e6c424b82224b85b64f28fd85761280?tpId=196&tqId=37077&ru=/exam/oj
	 * 关键词:递归 回溯 dfs 枚举
	 *
	 * 请编写一个程序，给数独中的剩余的空格填写上数字
	 * 空格用字符'.'表示
	 * 假设给定的数独只有唯一的解法
	 */
	virtual void solveSudoku(std::vector<std::vector<char> >& board) = 0;
};

class Sudoku
{
public:
	class EnumerateBacktrace :public ISudoku
	{
	public:
		void solveSudoku(std::vector<std::vector<char> >& board) override
		{
			if (!board.size() || !board[0].size())
				return;
			helper(board, 0, 0);
			return;
		}
	private:
		bool helper(std::vector<std::vector<char> >& board, int row, int col)
		{
			if (row == 9) { // 如果当前行都被填满了，则说明到当前行为止是成功的
				return true;
			}
			if (col == 9) { // 若达到；1最后一列，则从下一行的第一列重新开始填
				return helper(board, row + 1, 0);
			}
			if (board[row][col] != '.') // 如果没有被填
				return helper(board, row, col + 1);
			for (int i = 1; i <= 9; i++) { // 遍历1到9
				if (judgeValid(board, row, col, i)) { // 如果填的当前数字不冲突
					board[row][col] = (i + '0'); // 填写
					if (helper(board, row, col + 1)) // 剪枝
						return true;
					else
						board[row][col] = '.'; // 重置
				}
			}
			return false; // 遍历1到9后仍未得到结果，返回false
		}
		bool judgeValid(std::vector<std::vector<char> >& board, int row, int col, int target)
		{
			char ch = target + '0';
			int blockRow = (row / 3) * 3, blockCol = (col / 3) * 3;
			for (int i = 0; i < 9; i++) { // 判断行、列
				if (board[row][i] == ch || board[i][col] == ch)
					return false;
				// 判断方块
				if (board[blockRow + i / 3][blockCol + i % 3] == ch)
					return false;
			}
			return true;
		}
	};
	class Bit :public ISudoku
	{
	private:
		int line[9];
		int column[9];
		int block[3][3];
		bool valid;
		std::vector<std::pair<int, int>> spaces;//存储要填入的位置
	public:
		void solveSudoku(std::vector<std::vector<char>>& board) override
		{
			memset(line, 0, sizeof(line));
			memset(column, 0, sizeof(column));
			memset(block, 0, sizeof(block));
			valid = false;
			for (int i = 0; i < 9; ++i) {
				for (int j = 0; j < 9; ++j) {
					if (board[i][j] == '.') {
						//要是没有填入直接放入spaces 进行填入
						spaces.emplace_back(i, j);
						//emplace_back省去了移动构造函数 效率高
					}
					else {
						int digit = board[i][j] - '0' - 1;
						flip(i, j, digit);
					}
				}
			}
			dfs(board, 0);
		}
	private:
		void flip(int i, int j, int digit)
		{
			line[i] ^= (1 << digit);//利用二进制压缩来表示行
			column[j] ^= (1 << digit);//利用二进制压缩来表示列
			block[i / 3][j / 3] ^= (1 << digit);//利用二进制要是来表示小数组
		}
		void dfs(std::vector<std::vector<char>>& board, int pos)
		{
			if (pos == spaces.size()) {
				valid = true;
				return;
			}

			auto [i, j] = spaces[pos];
			//0x1ff 表示全为1 表全部填入了数字
			int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
			for (; mask && !valid; mask &= (mask - 1)) {
				int digitMask = mask & (-mask);
				//找到最低位的非0位置
				int digit = 0;
				// __builtin_ctz(digitMask);
				//内置函数__builtin_ctz：返回前导的0的个数。
				while (digitMask > 0 && (digitMask & 0x1) == 0)
				{
					digitMask >>= 1;
					digit++;
				}

				//回溯
				flip(i, j, digit);
				board[i][j] = digit + '0' + 1;
				dfs(board, pos + 1);
				flip(i, j, digit);
			}
		}
	};
public:
	class Solution :public ISudoku
	{
	private:
		std::vector<std::tuple<int, int>> fillableChars;
	public:
		void solveSudoku(std::vector<std::vector<char>>& boardChars) override
		{
			const int rowSize = boardChars.size();
			if (rowSize <= 0)
				return;
			const int colSize = boardChars.front().size();
			if (colSize <= 0)
				return;

			fillableChars.clear();
			for (int i = 0; i < rowSize; ++i)
				for (int j = 0; j < colSize; ++j)
				{
					if (boardChars[i][j] == '.')
						fillableChars.emplace_back(std::make_tuple(i, j));
				}

			EXPECT_TRUE(fillNums(boardChars, fillableChars.begin()));
		}
	private:
		bool fillNums(std::vector<std::vector<char>>& boardChars, std::vector<std::tuple<int, int>>::iterator fillPos)
		{
			//数独填充成功
			if (fillPos == fillableChars.end())
				return true;

			const int posX = std::get<0>(*fillPos);
			const int posY = std::get<1>(*fillPos);
			for (char num = '1'; num <= '9'; ++num)
			{
				if (canFillNumAt(boardChars, posX, posY, num))
				{
					boardChars[posX][posY] = num;
					if (fillNums(boardChars, fillPos + 1))
						return true;
					boardChars[posX][posY] = '.';
				}
			}
			return false;
		}
		bool canFillNumAt(std::vector<std::vector<char>>& boardChars,int x,int y,char num)
		{
			const int rowStart = x / 3 * 3;
			const int colStart = y / 3 * 3;

			//数独上每行、每列、每个宫都是9个数字
			for (int i = 0; i < 9; ++i)
			{
				//行中没有重复的字符
				if (boardChars[x][i] == num)
					return false;
				//列中没有重复的字符
				if (boardChars[i][y] == num)
					return false;
				//宫中没有重复的字符
				if (boardChars[rowStart + i / 3][colStart + i % 3] == num)
					return false;
			}
			return true;
		}
	};
};


#ifdef DEV_TEST
#include <gtest/gtest.h>
class SudokuTest:public SolutionTestor<ISudoku>
{
protected:
	void LoadSolutions(std::vector<ISudoku*>& solutions) override
	{
		solutions = {
			//new Sudoku::EnumerateBacktrace,
			//new Sudoku::Bit,
			new Sudoku::Solution,
		};
	}
};

TEST_F(SudokuTest, solveSudoku)
{
	TestForSolutions([](ISudoku* solution)
		{
			const std::string formatedInput = "[[.,.,9,7,4,8,.,.,.],[7,.,.,.,.,.,.,.,.],[.,2,.,1,.,9,.,.,.],[.,.,7,.,.,.,2,4,.],[.,6,4,.,1,.,5,9,.],[.,9,8,.,.,.,3,.,.],[.,.,.,8,.,3,.,2,.],[.,.,.,.,.,.,.,.,6],[.,.,.,2,7,5,9,.,.]]";
			const std::string formatedOutput = "[[5,1,9,7,4,8,6,3,2],[7,8,3,6,5,2,4,1,9],[4,2,6,1,3,9,8,7,5],[3,5,7,9,8,6,2,4,1],[2,6,4,3,1,7,5,9,8],[1,9,8,5,2,4,3,6,7],[9,7,5,8,6,3,1,2,4],[8,3,2,4,9,1,7,5,6],[6,4,1,2,7,5,9,8,3]]";

			std::vector<std::vector<char>> boardChars;
			FormatedUtil::parseFormated(boardChars, formatedInput);
			solution->solveSudoku(boardChars);

			EXPECT_EQ(FormatedUtil::dumpFormated(boardChars), formatedOutput);
		});

}
#endif